import java.util.*;

public class ChangeMaker
{
	
	// Store the available coins
	private Set<Coin> coins;
	// Store precomputed results
	private Map<Integer, Node<Coin>> results;
	
	/**
	 * Initialize the change maker, initializing the set of coins with
	 *   a "penny" to ensure change can always be made
	 */
	public ChangeMaker()
	{
		coins = new HashSet<Coin>();
		results = new HashMap<Integer, Node<Coin>>();
		coins.add(new Coin(1));
	}
	
	/**
	 * addCoin -- add a coin for use in change making; since this may
	 *   change results, the precomputed results should be cleared
	 * @param c the coin to be added
	 */
	public void addCoin(Coin c)
	{
		results.clear();
		coins.add(c);
	}
	
	/**
	 * countCoins -- return the number of coins contained in the list
	 * @param list the head of the list
	 * @return the number of coins in the list
	 */
	public static int countCoins(Node<Coin> list)
	{
		int n = 0;
		while (list != null)
		{
			n++;
			list = list.getNext();
		}
		return n;
	}
	
	/**
	 * makeChange -- return a list of the minimum number of coins
	 *   needed to make change for the given amount
	 * @param amt the amount to make change for
	 * @return the head of the list of coins
	 */
	public Node<Coin> makeChange(int amount)
	{
		// Basic Case
		if (amount == 0){
			return null;
		}	
		// Recursive Case
		// try to use the exist result before recursive
		if (results.containsKey(amount)){
			return results.get(amount);
		}
		
		// recursive
		Node<Coin> best = null;
		Node<Coin> curr = null;
		int min = amount;
		Iterator<Coin> itor = coins.iterator();
		
		while (itor.hasNext()){
			Coin c = itor.next();
			if (amount < c.getValue()){
				continue;
			}
			
			curr = new Node<Coin>(c,null);
			curr.setNext(makeChange(amount-c.getValue()));
			if ( countCoins(curr) <= min){
				best = curr;
				min = countCoins(best);
			}
		}
		
		// store the intermedia best combinations into the hashmap
		results.put(amount, best);
		return best;
		//throw new RuntimeException("You must implement this method!");
	}
	
	// A sample driver; TODO add your own tests!
	public static void main(String[] args)
	{
		ChangeMaker cm = new ChangeMaker();
		
		cm.addCoin(new Coin(10));
		cm.addCoin(new Coin(25));
		cm.addCoin(new Coin(21));
		cm.addCoin(new Coin(5));
		
		System.out.println("7:  " + cm.makeChange(7));
		System.out.println("16: " + cm.makeChange(16));
		System.out.println("42: " + cm.makeChange(42));
		System.out.println("63: " + cm.makeChange(63));
		System.out.println("2: " + cm.makeChange(2));
	}
	
}
